МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра автоматизованих систем управління
/
Лабораторна робота №3-4
з дисципліни “Математичні методи дослідження операцій”
на тему
«Симплекс метод »
Мета роботи: вивчення симплекс методу для знаходження розв’язку задач лінійного програмування .
План
Короткі теоретичні відомості.
Постановка задачі
Симплекс метод розв’язаний за допомогою симплекс таблиць Жордана Гауса
Симплекс метод розв’язаний за допомогою симлекс таблиць з додаванням змінних.
Розв’язання за допомогою пакету програм SimplexWin
Розв’язання за допомогою власної програми.
Хід роботи
1. Короткі теоретичні відомості
Симплекс метод - універсальний метод для вирішення лінійної системи рівнянь або нерівностей і лінійного функціоналу.
Для приведення системи обмежень нерівностей до канонічного виду, необхідно в системі обмежень виділити одиничний базис.
I. Обмеження виду «» - ресурсні обмеження. Справа знаходиться те що ми використовуємо на виробництві, ліворуч - те що отримуємо. При таких обмеженнях вводять додаткові змінні з коефіцієнтом «+1», що утворюють одиничний базис. У цільову функцію ці змінні увійдуть з коефіцієнтом «0».
II. Обмеження виду «=». Часто буває, що незважаючи на те що обмеження мають вигляд рівності, одиничний базис не виділяється або важко виділяється. В цьому випадку вводяться штучні змінні для створення одиничного базису - Yi. В систему обмежень вони входять з коефіцієнтом «1», а в цільову функцію з коефіцієнтом «M», що прагнуть до нескінченності (при Fmin - «+ M», при Fmax - «-M»).
III. Обмеження виду «» - планові обмеження. Додаткові змінні (X), що несуть певний економічний зміст - перевитрата ресурсів або перевиконання плану, перевиробництво, додаються з коефіцієнтом «-1», в цільову функцію - з коефіцієнтом «0». А штучні змінні (Y) як у попередньому випадку.
Алгоритм симплекс методу
Нехай система приведена до канонічного виду.
X1+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1
X2+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1 (1)
X3+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1
……………………………………………………………….
Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm
У ній m базисних змінних, k вільних змінних. m + k = n - всього змінних.
Fmin = C1X1 + C2X2 + C3X3 + .... + CnXn
Всі hi повинні бути більше або дорівнюють нулю, де i = 1,2 ... m. На першому кроці в якості допустимого рішення приймаємо всі Xj = 0 (j = m +1, m +2, ..., m + k). При цьому всі базисні змінні Xi = Hi.
Для подальших міркувань обчислень будемо користуватися першою симплекс таблицею.
Таблица 1 –Перша симплес таблиця .
C
Б
H
C1
C2
…
Cm
Cm+1
…
Cm+k
X1
X2
…
Xm
Xm+1
…
Xm+k
C1
C2
C3
:
:
Cm
X1
X2
X3
:
:
Xm
h1
h2
h3
:
:
hm
1
0
0
:
:
0
0
1
0
:
:
0
:
:
:
:
:
:
0
0
0
:
:
0
q1,m+1
q2,m+1
q3,m+1
:
:
qm,m+1
:
:
:
:
:
:
q1,m+k
q2,m+k
q3,m+k
:
:
qm,m+k
F=
F0
…
m
m+1
…
m+k
Перший стовпчик-коефіцієнти в цільової функції при базисних змінних.
Другий стовпчик - базисні змінні.
Третій стовпчик - вільні члени (hi0).
Самий верхній рядок - коефіцієнти при цільовій функції.
Другий верхній рядок - змінні, що входять в цільову функцію і в систему обмежень.
Основне поле симплекс методу - система коефіцієнтів з рівняння.
Останній рядок - служить для того, щоб відповісти на питання: «оптимальний план чи ні».
2. Постановка задачі
Розв’язати задачу лінійного програмування симплекс методом (номер завдання відповідає двом останнім цифрам залікової книжки студента, крім цифр 00 – які відповідають завданню під номером100)
Варіант 48
F(x1,x2) = 3x1 + 6x2 max ;
x1 + x2 8,
3x1 + 7x2 21,
x1 + 2x2 6,
0x1 7, 0x2 7.
2.1 Розв’язання без використання пакетів програм.
Cимплекс метод розв’язаний за допомогою сиплекс таблиць
Жордана -Гауса.
Для того щоб показати , що я освоїв даний матеріал зміню напрям цільової функції на min . Оскільки в даній лабораторній роботі розглядається і сиплекс метод двійної задачі то в наступному методі буде показано зн...